package course.p4_list.s1_OneNextList;

/**
 * 链表算法
 */
public class ListAlgorithm {
    /**
     * 链表节点数据结构
     */
    static class Node {
        /**
         * 存储节点数据
         */
        private int data;
        /**
         * 存储下一个节点引用
         */
        private Node next;
        /**
         * 本节点名称
         */
        private String nodeName;
        /**
         * 节点构造方法，仅构造出其存储的数据，并不构造下一节点的引用
         * @param data 节点数据
         */
        public Node(int data, String nodeName) {
            this.data=data;
            if(nodeName==null){
                nodeName=""+data;
            }
            this.nodeName=nodeName;
        }
    }
    
    /**
     * 以输入节点为头，计算出链表长度
     * @param head 头节点
     * @return 链表长度
     */
    static int listLength(Node head) {
        int length = 0;
        Node current = head;
        while(current!=null){
            length++;
            current = current.next;
        }
        return length;
    }

    /**
     * 链表节点插入
     * 主要思路是：先判断链表中存不存在position位置，若没有输出错误信息并返回头节点；
     *      若存在则进行插入操作：首先判断position是不是为1，因为这种情况不同于其他的。
     *      否则，先找到第position-1个节点和position个节点，将前一个节点的下一节点设为nodeToInsert
     *      将nodeToInsert的下一个节点设置为position节点，这样完成插入操作
     * @param head 链表头节点
     * @param insert 要插入的节点
     * @param position 指定插入的位置
     * @return 插入后的链表头节点
     */
    static Node insertInLinkedList(Node head, Node insert, int position) {
        if(head == null) {
            return insert;
        }
        //获得输入链表的长度
        int size = listLength(head);
        //判断链表内是否存在此位置
        if(position>size||position<0) {
            System.out.println("链表不存在该位置： "+ position +"链表最大位置索引： "+(size-1));
            return head;
        }
        //在链表开头插入
        if(position==0) {
            insert.next = head;
            return insert;
        }
        //在中间或末尾插入
        else{
            Node pre = head;
            //找到那个位置的前一个节点
            for(int index = 0;index < position-1;index++){
                //获得第position-1位置的节点
                pre = pre.next;
            }
            //插入操作
            insert.next = pre.next;
            pre.next = insert;
        }
        return head;
    }

    /**
     * 方法和前面的插入方法有异曲同工之妙：
     *  主要思想是找到position的前一个节点和后一个节点，然后将他们连接
     * @param head 头节点
     * @param position 删除的位置
     * @return 删除后的链表头节点
     */
    static Node deleteNodeFromLinkedList(Node head, int position) {
        int size = listLength(head);
        if(position > size||position < 0) {
            System.out.println("链表不存在该位置： "+ position +"链表最大位置索引： "+(size-1));
            return head;
        }
        //删除表头
        if(position == 0){
            return head.next;
        }
        //删除中间或结尾节点
        else{
            Node pre = head;
            //获得目标节点的上一个节点
            for(int index = 0;index < position-1;index++) {
                pre = pre.next;
            }
            //要删除目标节点
            Node cur = pre.next;
            pre.next = cur.next;
        }
        return head;
    }

    /**
     * 修改指定位置的值
     * @param head
     * @param position
     * @param element
     * @return
     */
    static Node updateNode(Node head, int position,int element) {
        int size = listLength(head);
        if(position < 0 || position >= size) {
            System.out.println("链表不存在该位置： "+ position +"链表最大位置索引： "+(size-1));
        }
        Node cur = head;
        for(int index = 0;index < position;index++){
            cur = cur.next;
        }
        cur.data = element;
        return head;
    }

    /**
     * 获取链表指定位置的元素
     * @param head
     * @param position
     * @return
     */
    static Node get(Node head,int position) {
        int size = listLength(head);
        if(position<0||position>=size) {
            System.out.println("链表不存在该位置： "+ position +"链表最大位置索引： "+(size-1));
        }
        Node cur = head;
        for (int index = 0;index < position;index++){
            cur = cur.next;
        }
        return cur;
    }

    /**
     * 遍历打印链表内容
     * @param headNode 链表头节点
     */
    static void toString(Node headNode) {
        Node check = headNode;
        if(check==null){
            System.out.print("null");
            return;
        }
        for(;;){
            System.out.print(check.nodeName+"->");
            check = check.next;
            if(check == null){
                System.out.println("null");
                break;
            }
        }
    }

}
